package C036;

/**
 * ClassName: C10
 * Package: C036
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/1/21 22:00
 * @Version 1.0
 * @Since 1.0
 */
public class C10 {
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        System.out.println(countNodes(treeNode1));
    }
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    // 找出完全二叉树的节点的个数
    public static int countNodes(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return process(root, 1, high(root, 1)); // 目前的高度， 最高的高度
    }
    private static int process(TreeNode root, int curLevel, int high) {
        if(curLevel == high) {
            return 1;
        }

        // 左子树达到最高的高度，证明右树是满二叉树
        if(high(root.right, curLevel + 1) == high) {
            return (1 << (high - curLevel)) + process(root.right, curLevel + 1, high);
        } else { // 反之
            return (1 << (high - curLevel - 1)) + process(root.left, curLevel + 1, high);
        }
    }


    public static int high(TreeNode node, int curLevel) {
        if(node == null) {
            return curLevel - 1;
        }
        node = node.left;
        while(node != null) {
            curLevel++;
            node = node.left;
        }
        return curLevel;
    }
}
